#include "trees.h"
#include "simple-tree.h"
#include <list>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

template <class V, class E>
Trees::SimpleTree<V,E>::SimpleTree(const V& value) 
		: DynamicTree<V,E>(value), m_parent(NULL), m_cost(0)
{
}

template <class V, class E>
Trees::SimpleTree<V,E>::~SimpleTree()
{
}

template <class V, class E>
const V Trees::SimpleTree<V,E>::Value() const
{
	return DynamicTree<V,E>::Value();
}

template <class V, class E>
Trees::SimpleTree<V,E>* Trees::SimpleTree<V,E>::Parent() const
{
	return m_parent;
}

template <class V, class E>
Trees::SimpleTree<V,E>* Trees::SimpleTree<V,E>::Root() const
{
//cerr << "Root >>> this=" << Value() << endl;
	Trees::SimpleTree<V,E>* t = const_cast<SimpleTree<V,E> *>(this);
	Trees::SimpleTree<V,E>* parent;
	while ( parent = t->Parent() )
	{
		t = parent;
//cerr << "Root: t=" << t->Value() << endl;		
	}
//cerr << "Root <<< return " << (t ? t->Value() : NULL) << endl;
	return t;
}

template <class V, class E>
const E Trees::SimpleTree<V,E>::Cost() const
{
	return m_cost;
}

template <class V, class E>
Trees::SimpleTree<V,E>* Trees::SimpleTree<V,E>::MinCost() const
{
//cerr << "MinCost(" << Value() << ") >>>" << endl;	
	if ( !Parent() )
	{
		throw IllegalTreeOperationException();
	}
	SimpleTree<V,E>* minTree = const_cast<SimpleTree<V,E> *>(this);;
	E minCost = m_cost;
	SimpleTree<V,E>* t = Parent();
	SimpleTree<V,E>* parent;
	while ( parent = t->Parent() )
	{
		if ( t->m_cost <= minCost )
		{
			minCost = t->m_cost;
			minTree = t;
		}
		t = parent;
	}
//cerr << "MinCost(" << Value() << ") <<<" << endl;	
	return minTree;
}

template <class V, class E>
void Trees::SimpleTree<V,E>::Update(const E& x)
{
	SimpleTree<V,E>* t = this;
	do
	{
		t->m_cost = sum(t->m_cost, x);
		t = t->Parent();
	}
	while ( t );
}

template <class V, class E>
void Trees::SimpleTree<V,E>::Link(DynamicTree<V,E>* otherRoot, const E& x)
{
//cerr << "Link(" << otherRoot->Value() << " -> " << Value() << ") >>>" << endl;	
	SimpleTree<V,E>* v = dynamic_cast<SimpleTree<V,E> *>(otherRoot);
	v->m_parent = this;
	v->m_cost = x;
//cerr << "Link(" << otherRoot->Value() << " -> " << Value() << ") <<<" << endl;	
}

template <class V, class E>
const E Trees::SimpleTree<V,E>::Cut()
{
//cerr << "Cut(" << Value() << ") >>>" << endl;	
	if ( !m_parent )
	{
		throw new IllegalTreeOperationException();
	}
	m_parent = 0;
//cerr << "Cut(" << Value() << ") <<<" << endl;		
	return m_cost;
}

template <class V, class E>
void Trees::SimpleTree<V,E>::Evert()
{
//cerr << "Evert(" << Value() << ") >>> " << endl;
	SimpleTree<V,E>* newParent = 0;
	E cost;
	SimpleTree<V,E>* t = this;
	
	while ( t )
	{
		SimpleTree<V,E>* oldParent = t->m_parent;
		E oldCost = t->m_cost;

		t->m_parent = newParent;
		t->m_cost = cost;

		newParent = t;
		t = oldParent;
		cost = oldCost;
	}
//cerr << "Evert(" << Value() << ") <<< " << endl;
}

template class Trees::SimpleTree<int,int>;
template class Trees::SimpleTree<int, Trees::EdgeInfo<int> >;
